Stack, Queues & Recursion

Stack

/*Runtime exception thrown when one tries to perform operation top or pop on an empty stack*/

Method         Time

size                 O(1)

isEmpty         O(1)

top                 O(1)

push               O(1)

pop                O(1)

Stacks in the Java Virtual Machine

A java program is typically compiled into a sequence of byte codes that are defined as "machine" instructions for a well-defined model - the JAVA VIRTUAL MACHINE (JVM).

The definition of JVM is at the heart of the definition of the java language itself.

By compiling java code into the JVM bytes codes, rather than the machine language of a specific CPU, a java program can be run on any computer, such as a personal computer or a server, that has a program that can evaluate the JVM.

Interestingly, the stacks data structure plays a central role in the definition of the JVM.

Frames: during the execution of a java program, the JVM maintains a stack whose elements are descriptors of the currently active invocations of methods. These descriptions are called frames.

Program Counter: The JVM keeps a spectial variables, called the program counter, to maintain the address of the statement the JVM id currently executing in the program.

Running Method: At the top of the java stack is the frame of the running method, that is, the method that currently has control of the execution.

Suspended Methods: The methods that have invoked another method and are currently waiting for it to return control to them upon its termination.

When a new method is invoked, a frame for this method is pushed onto the stack. When it terminates, its frames is popped from the stack and the JVM resumes the processing of the previously suspended method.