Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... , a stack is an abstract data type
Abstract data type
In computing, an abstract data type is a specification of a set of data and the set of operations that can be performed on the data. Such a data type is abstract in the sense that it is independent of various concrete implementations.... and data structure
Data structure
A data structure in computer science is a way of storing data in a computer so that it can be used efficiently. It is an organization of mathematical and logical concepts of data.... based on the principle of Last In First Out (LIFO). Stacks are used extensively at every level of a modern computer system. For example, a modern PC uses stacks at the architecture level
Computer architecture
Computer architecture in computer engineering is the conceptual design and fundamental operational structure of a computer system. It is a blueprint and functional description of requirements and design implementations for the various parts of a computer, focusing largely on the way by which the central processing unit performs internally an... , which are used in the basic design of an operating system for interrupt handling and operating system function calls. Among other uses, stacks are used to run a Java Virtual Machine
Java Virtual Machine
A Java Virtual Machine is a set of computer software programs and data structures which use a virtual machine model for the execution of other computer programs and Scripting language.... , and the Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java .... language itself has a class called "Stack", which can be used by the programmer.
Discussion
Ask a question about 'Stack (data structure)'
Start a new discussion about 'Stack (data structure)'
Computer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems.... , a stack is an abstract data type
Abstract data type
In computing, an abstract data type is a specification of a set of data and the set of operations that can be performed on the data. Such a data type is abstract in the sense that it is independent of various concrete implementations.... and data structure
Data structure
A data structure in computer science is a way of storing data in a computer so that it can be used efficiently. It is an organization of mathematical and logical concepts of data.... based on the principle of Last In First Out (LIFO). Stacks are used extensively at every level of a modern computer system. For example, a modern PC uses stacks at the architecture level
Computer architecture
Computer architecture in computer engineering is the conceptual design and fundamental operational structure of a computer system. It is a blueprint and functional description of requirements and design implementations for the various parts of a computer, focusing largely on the way by which the central processing unit performs internally an... , which are used in the basic design of an operating system for interrupt handling and operating system function calls. Among other uses, stacks are used to run a Java Virtual Machine
Java Virtual Machine
A Java Virtual Machine is a set of computer software programs and data structures which use a virtual machine model for the execution of other computer programs and Scripting language.... , and the Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java .... language itself has a class called "Stack", which can be used by the programmer. The stack is ubiquitous.
A stack-based computer system is one that stores temporary information primarily in stacks, rather than hardware CPU registers
Processor register
In computer architecture, a processor register is a small amount of Computer storage available on the CPU whose contents can be accessed more quickly than storage available elsewhere.... (a register-based computer system).
History
The stack method of expression evaluation was first proposed in 1955 and then patented in 1957 by early German computer scientist Friedrich L. Bauer
Friedrich L. Bauer
Friedrich Ludwig Bauer is a Germany computer scientist and Emeritus at Technical University of Munich.... , who received the IEEE Computer Society Pioneer Award in 1988 for his work on Computer Stacks. Apparently the same concept was introduced independently by the Australian scientist Charles Leonard Hamblin
Charles Leonard Hamblin
Charles Leonard Hamblin was an Australian philosopher, logician and a computer pioneer as well as a professor for philosophy at the Technical University of New South Wales in Sydney.... .
In computing, an abstract data type is a specification of a set of data and the set of operations that can be performed on the data. Such a data type is abstract in the sense that it is independent of various concrete implementations.... , the stack is a container
Container (data structure)
In computer science, a container is a Class , a data structure, or an abstract data type whose instances are collections of other objects. They are used to store objects in an organized way following specific access rules.... of node
Node (computer science)
A node is an abstract basic unit used to build linked data structures such as tree data structure, linked lists, and computer-based representations of graph .... s and has two basic operations: push and pop. Push adds a given node to the top of the stack leaving previous nodes below. Pop removes and returns the current top node of the stack. A frequently used metaphor is the idea of a stack of plates in a spring loaded cafeteria stack. In such a stack, only the top plate is visible and accessible to the user, all other plates remain hidden. As new plates are added, each new plate becomes the top of the stack, hiding each plate below, pushing the stack of plates down. As the top plate is removed from the stack, they can be used, the plates pop back up, and the second plate becomes the top of the stack. Two important principles are illustrated by this metaphor: the Last In First Out principle is one; the second is that the contents of the stack are hidden. Only the top plate is visible, so to see what is on the third plate, the first and second plates will have to be removed. This can also be written as FILO-First In Last Out, i.e. the record inserted first will be popped out at last.
Operations
In modern computer languages, the stack is usually implemented with more operations than just "push" and "pop". The length of a stack can often be returned as a parameter. Another helper operation top (also known as peek) can return the current top element of the stack without removing it from the stack.
Pseudocode is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of some programming language, but is intended for human reading rather than machine reading.... for adding or removing nodes from a stack, as well as the length and top functions. Throughout we will use null
Null
Null is an English word meaning 'nothing' or without value or consequence. It is derived from the Latin word nullus meaning 'none'.Null may refer to:... to refer to an end-of-list marker or sentinel value
Sentinel value
In computer programming, a sentinel value is a special value that is used to terminate a Control flow that processes data structure data . The value should be selected in such a way that it will not be confused with legal data values.... , which may be implemented in a number of ways using pointers.
recordNode
recordStack
function push(Stack stack, Element element)
function pop(Stack stack)
function top(Stack stack)
function length(Stack stack)
As you can see, these functions pass the stack and the data elements as parameters and return values, not the data nodes that, in this implementation, include pointers. A stack may also be implemented as a linear section of memory (i.e. an array), in which case the function headers would not change, just the internals of the functions.
Implementation
A typical storage requirement for a stack of n elements is O
Big O notation
In mathematics, big O notation describes the asymptotic analysis of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.... (n). The typical time requirement of O
Big O notation
In mathematics, big O notation describes the asymptotic analysis of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.... (1) operations is also easy to satisfy with a dynamic array
Dynamic array
In computer science, a dynamic array, growable array, resizable array, dynamic table, or array list is an array data structure that can be resized and allows elements to be added or removed.... or (singly) linked list
Linked list
In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of node s, each containing arbitrary data Field s and one or two reference s pointing to the next and/or previous nodes.... implementation.
The Standard Template Library is a Library partially included in the C++ C++ standard library. It provides Container s, iterators, algorithms, and Function objects.... provides a "stack" templated class which is restricted to only push/pop operations. Java's library contains a class that is a specialization of . This could be considered a design flaw because the inherited get method from ignores the LIFO constraint of the .
Here is a simple example of a stack with the operations described above (but no error checking) in Python
Python (programming language)
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python's core syntax and semantics are Minimalism , while the standard library is large and comprehensive.... .
class Stack(object):
def __init__(self):
self.stack_pointer = None
def push(self, element):
self.stack_pointer = Node(element, self.stack_pointer)
def pop(self):
e = self.stack_pointer.element
self.stack_pointer = self.stack_pointer.next
return e
def peek(self):
return self.stack_pointer.element
def __len__(self):
i = 0
sp = self.stack_pointer
while sp:
i += 1
sp = sp.next
return i
class Node(object):
def __init__(self, element=None, next=None):
self.element = element
self.next = next
if __name__
'__main__':
# small use example
s = Stack
[s.push(i) for i in xrange(10)]
print [s.pop for i in xrange(len(s))]
The above is admittedly redundant as Python supports the 'pop' and 'append' functions to lists.
Related data structures
The abstract data type and data structure of the First In First Out (FIFO) principle is the queue, and the combination of stack and queue operations is provided by the deque
Deque
In computer science theory, a deque is an abstract data structure, also called a head-tail linked list, for which elements can only be added to or removed from the front or back .... . For example, changing a stack into a queue in a search algorithm
Search algorithm
In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions.... can change the algorithm from depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree data structure, tree structure, or graph . One starts at the root and explores as far as possible along each branch before backtracking.... (DFS) into a breadth-first search
Breadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.... (BFS). A bounded stack is a stack limited to a fixed size.
Hardware stacks
A common use of stacks at the Architecture level is as a means of allocating and accessing memory.
Basic architecture of a stack
A typical stack is an area of computer memory with a fixed origin and a variable size. Initially the size of the stack is zero. A stack pointer, usually in the form of a hardware register, points to the most recently referenced location on the stack; when the stack has a size of zero, the stack pointer points to the origin of the stack.
The two operations applicable to all stacks are:
a push operation, in which a data item is placed at the location pointed to by the stack pointer, and the address in the stack pointer is adjusted by the size of the data item;
a pop or pull operation: a data item at the current location pointed to by the stack pointer is removed, and the stack pointer is adjusted by the size of the data item.
There are many variations on the basic principle of stack operations. Every stack has a fixed location in memory at which it begins. As data items are added to the stack, the stack pointer is displaced to indicate the current extent of the stack, which expands away from the origin (either up or down, depending on the specific implementation).
For example, a stack might start at a memory location of one thousand, and expand towards lower addresses, in which case new data items are stored at locations ranging below 1000, and the stack pointer is decremented each time a new item is added. When an item is removed from the stack, the stack pointer is incremented.
Stack pointers may point to the origin of a stack or to a limited range of addresses either above or below the origin (depending on the direction in which the stack grows); however, the stack pointer cannot cross the origin of the stack. In other words, if the origin of the stack is at address 1000 and the stack grows downwards (towards addresses 999, 998, and so on), the stack pointer must never be incremented beyond 1000 (to 1001, 1002, etc.). If a pop operation on the stack causes the stack pointer to move past the origin of the stack, a stack underflow occurs. If a push operation causes the stack pointer to increment or decrement beyond the maximum extent of the stack, a stack overflow occurs.
Some environments that rely heavily on stacks may provide additional operations, for example:
Dup(licate): the top item is popped and pushed again so that an additional copy of the former top item is now on top, with the original below it.
Peek: the topmost item is popped, but the stack pointer is not changed, and the stack size does not change (meaning that the item remains on the stack). This is also called top operation in many articles.
Swap or exchange: the two topmost items on the stack exchange places.
Rotate: the n topmost items are moved on the stack in a rotating fashion. For example, if n=3, items 1, 2, and 3 on the stack are moved to positions 2, 3, and 1 on the stack, respectively. Many variants of this operation are possible, with the most common being called left rotate and right rotate.
Stacks are either visualized growing from the bottom up (like real-world stacks), or, with the top of the stack in a fixed position (see image), a , a Pez
PEZ
PEZ is the brand name of an Austria candy and the pocket mechanical dispensers for such candy. The candy takes the shape of pressed, dry, straight-edged blocks , with PEZ dispensers holding 12 pieces of PEZ candy.... dispenser, or growing from left to right, so that "topmost" becomes "rightmost". This visualization may be independent of the actual structure of the stack in memory. This means that a right rotate will move the first element to the third position, the second to the first and the third to the second. Here are two equivalent visualisations of this process:
applebanana
banana
right rotate
> cucumber
cucumber apple
cucumber apple
banana
left rotate
> cucumber
applebanana
A stack is usually represented in computers by a block of memory cells, with the "bottom" at a fixed location, and the stack pointer holding the address of the current "top" cell in the stack. The top and bottom terminology are used irrespective of whether the stack actually grows towards lower memory addresses or towards higher memory addresses.
Pushing an item on to the stack adjusts the stack pointer by the size of the item (either decrementing or incrementing, depending on the direction in which the stack grows in memory), pointing it to the next cell, and copies the new top item to the stack area. Depending again on the exact implementation, at the end of a push operation, the stack pointer may point to the next unused location in the stack, or it may point to the topmost item in the stack. If the stack points to the current topmost item, the stack pointer will be updated before a new item is pushed onto the stack; if it points to the next available location in the stack, it will be updated after the new item is pushed onto the stack.
Popping the stack is simply the inverse of pushing. The topmost item in the stack is removed and the stack pointer is updated, in the opposite order of that used in the push operation.
A central processing unit is an electronic circuit that can execute computer programs. This broad definition can easily be applied to many early computers that existed long before the term "CPU" ever came into widespread usage.... have registers that can be used as stack pointers. Some, like the Intel
Intel Corporation
Intel Corporation is the world's largest semiconductor company and the inventor of the X86 architecture series of microprocessors, the processors found in most personal computers.... x86, have special instructions that implicitly use a register dedicated to the job of being a stack pointer. Others, like the DEC
Digital Equipment Corporation
Digital Equipment Corporation was a pioneering United States company in the computer industry. It is often referred to within the computing industry as DEC .... PDP-11
PDP-11
The PDP-11 was a series of 16-bit minicomputers sold by Digital Equipment Corporation from 1970 into the 1990s. Though not explicitly conceived as successor to DEC's PDP-8 computer in the Programmed Data Processor series of computers , the PDP-11 replaced the PDP-8 in many Real-time computing.... and the Motorola
Motorola
Motorola, Inc. is an United States, multinational, Fortune 100, telecommunications company based in Schaumburg, Illinois. It is a manufacturer of wireless telephone handsets, also designing and selling wireless network infrastructure equipment such as cellular transmission base stations and signal amplifiers.... 68000 family have addressing modes that make it possible to use any of a set of registers as a stack pointer.
Intel Corporation is the world's largest semiconductor company and the inventor of the X86 architecture series of microprocessors, the processors found in most personal computers.... 80x87
Intel 8087
The 8087 was the first math coprocessor for 16 bit processors designed by Intel ; it was built to be paired with the Intel Intel 8088 and Intel 8086 microprocessors.... series of numeric coprocessors has a set of registers that can be accessed either as a stack or as a series of numbered registers.
Sun's SPARC
SPARC
SPARC is a Reduced Instruction Set Computer microprocessor instruction set Computer architecture originally designed in 1985 by Sun Microsystems.... has a number of register windows organized as a stack which significantly reduces the need to use memory for passing function's arguments and return values.
stack in separate stack memory
There are also a number of microprocessors which implement a stack directly in hardware:
Some microcontroller
Microcontroller
A microcontroller is a small computer on a single integrated circuit consisting of a relatively simple CPU combined with support functions such as a crystal oscillator, timers, watchdog, serial and analog I/O etc.... s have a fixed-depth stack that is not directly accessible.
PIC is a family of Harvard architecture microcontrollers made by Microchip Technology, derived from the PIC1640 originally developed by General Instrument's Microelectronics Division.... s
Computer Cowboys MuP21
Harris RTX line
Novix NC4016
Many stack-based microprocessors were used to implement the programming language Forth at the microcode
Microcode
Microcode is a layer of lowest-level instructions involved in the implementation of machine code instructions in many computers and other processors; it resides in a special high-speed memory and translates machine instructions into sequences of detailed circuit-level operations.... level. Stacks were also used as a basis of a number of mainframes and mini computers. Such machines were called stack machines, the most famous being the Burroughs B5000.
Software support
In application programs written in a high level language, a stack can be implemented efficiently using either array
Array
In computer science, an array is a data structure consisting of a group of element s that are accessed by index . In most programming languages each element has the same data type and the array occupies a contiguous area of computer memory.... s or linked list
Linked list
In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of node s, each containing arbitrary data Field s and one or two reference s pointing to the next and/or previous nodes.... s. In LISP
Lisp
A lisp is a speech impediment, historically also known as sigmatism. Stereotypically, people with a lisp are unable to pronounce sibilants , and replace them with Interdental consonants , though there are actually several kinds of lisps.... there is no need to implement the stack, as the functions push and pop are available for any list. All Forth like languages (such as Adobe PostScript
PostScript
PostScript is a dynamically typed concatenative programming language programming language created by John Warnock and Charles Geschke in 1982. PostScript is best known for its use as a page description language in the electronic and desktop publishing areas.... ) are also designed around a stack that is directly visible to and manipulated by the programmer.
Reverse Polish notation by analogy with the related Polish notation, a prefix notation introduced in 1920 by the Poland mathematician Jan Lukasiewicz, is a mathematical notation wherein every operator follows all of its operands.... use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form needs a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context-free languages
Context-free grammar
In formal language theory, a context-free grammar is a formal grammar in which every Production rule is of the formwhere V is a single nonterminal symbol, and w is a string of Terminal and nonterminal symbolss and/or nonterminals .... allowing them to be parsed with stack based machines.
Example (general)
The calculation: ((1 + 2) * 4) + 3 can be written down like this in postfix notation with the advantage of no precedence rules and parentheses needed:
1 2 + 4 * 3 +
The expression is evaluated from the left to right using a stack:
push when encountering an operand and
pop two operands and evaluate the value when encountering an operation.
push the result
Like the following way (the Stack is displayed after Operation has taken place):
Input
Operation
Stack
1
Push operand
1
2
Push operand
1, 2
+
Add
3
4
Push operand
3, 4
*
Multiply
12
3
Push operand
12, 3
+
Add
15
The final result, 15, lies on the top of the stack at the end of the calculation.
begin
assign (f, cc);
reset (f);
read (f, cc);
if (cc = mark) then
begin
writeln ('empty archives !');
end
else
begin
repeat
if (IsOperand (cc)) then
begin
ccInt := ChrToInt (cc);
push (ccInt, data);
end
else
begin
pop (cc1, data);
pop (cc2, data);
push (data, Operator (cc2, cc1));
end;
read (f, cc);
until (cc = mark);
end;
close (f);
end.
A programming language is a machine-readable artificial language designed to express computations that can be performed by a machine, particularly a computer.... s are stack-oriented
Stack-oriented programming language
A stack-oriented programming language is one that relies on a stack machine model for passing parameters. Several programming languages fit this description, notably Forth and PostScript, and also many Assembly languages .... , meaning they define most basic operations (adding two numbers, printing a character) as taking their arguments from the stack, and placing any return values back on the stack. For example, PostScript
PostScript
PostScript is a dynamically typed concatenative programming language programming language created by John Warnock and Charles Geschke in 1982. PostScript is best known for its use as a page description language in the electronic and desktop publishing areas.... has a return stack and an operand stack, and also has a graphics state stack and a dictionary stack.
Forth uses two stacks, one for argument passing and one for subroutine return address
Return address
In postal mail, a return address is an explicit inclusion of the address of the person sending the message. It provides the recipient with a means to determine how to respond to the sender of the message if needed.... es. The use of a return stack is extremely commonplace, but the somewhat unusual use of an argument stack for a human-readable programming language is the reason Forth is referred to as a stack-based
Stack-oriented programming language
A stack-oriented programming language is one that relies on a stack machine model for passing parameters. Several programming languages fit this description, notably Forth and PostScript, and also many Assembly languages .... language.
In computer science, a virtual machine is a software implementation of a machine that executes programs like a real machine.Definitions... s are also stack-oriented, including the p-code machine
P-Code machine
In computer programming, a p-code machine or pseudo-code machine is a virtual machine designed to execute p-code . This term is applied both generically to all such machines , and to specific implementations, the most famous being the p-Machine of UCSD Pascal.... and the Java virtual machine
Java Virtual Machine
A Java Virtual Machine is a set of computer software programs and data structures which use a virtual machine model for the execution of other computer programs and Scripting language.... .
Almost all computer runtime memory environments use a special stack (the "call stack
Call stack
In computer science, a call stack is a dynamic Stack data structure that stores information about the active subroutines of a computer program.... ") to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes. They follow a runtime protocol between caller and callee to save arguments and return value on the stack. Stacks are an important way of supporting nested or recursive
Recursion
Recursion, in mathematics and computer science, is a method of defining Function in which the function being defined is applied within its own definition.... function calls. This type of stack is used implicitly by the compiler to support CALL and RETURN statements (or their equivalents) and is not manipulated directly by the programmer.
Some programming languages use the stack to store data that is local to a procedure. Space for local data items is allocated from the stack when the procedure is entered, and is deallocated when the procedure exits. The C programming language
C (programming language)
C is a general-purpose computer programming language originally developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories to implement the Unix operating system.... is typically implemented in this way. Using the same stack for both data and procedure calls has important security implications (see below) of which a programmer must be aware in order to avoid introducing serious security bugs into a program.
Security
Some computing environments use stacks in ways that may make them vulnerable to security breaches and attacks. Programmers working in such environments must take special care to avoid the pitfalls of these implementations.
For example, some programming languages use a common stack to store both data local to a called procedure and the linking information that allows the procedure to return to its caller. This means that the program moves data into and out of the same stack that contains critical return addresses for the procedure calls. If data is moved to the wrong location on the stack, or an oversized data item is moved to a stack location that is not large enough to contain it, return information for procedure calls may be corrupted, causing the program to fail.
Malicious parties may attempt to take advantage of this type of implementation by providing oversized data input to a program that does not check the length of input. Such a program may copy the data in its entirety to a location on the stack, and in so doing it may change the return addresses for procedures that have called it. An attacker can experiment to find a specific type of data that can be provided to such a program such that the return address of the current procedure is reset to point to an area within the stack itself (and within the data provided by the attacker), which in turn contains instructions that carry out unauthorized operations.
In computer security and computer programming, a buffer overflow, or buffer overrun, is an Anomaly in software condition where a process attempts to store data beyond the boundaries of a fixed-length buffer .... attack and is an extremely frequent source of security breaches in software, mainly because some of the most popular programming languages (such as C
C (programming language)
C is a general-purpose computer programming language originally developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories to implement the Unix operating system.... ) use a shared stack for both data and procedure calls, and do not verify the length of data items. Frequently programmers do not write code to verify the size of data items, either, and when an oversized or undersized data item is copied to the stack, a security breach may occur.
In computer science theory, a deque is an abstract data structure, also called a head-tail linked list, for which elements can only be added to or removed from the front or back ....
Stack s in computing architectures are regions of memory where data is added or removed in a LIFO manner.In most modern computer systems, each Thread has a reserved region of memory referred to as its stack....
A computer network is a group of interconnected computers. Networks may be classified according to a wide variety of characteristics. This article provides a general overview of some types and categories and also presents the basic components of a network.... ing term protocol stack
Protocol stack
A protocol stack is a particular software implementation of a computer networking protocol suite. The terms are often used interchangeably....
In computer science, a stack machine is a model of computation in which the computer's memory takes the form of one or more stack s. The term also refers to an actual computer implementing or simulating the idealized stack machine....
Donald Ervin Knuth is a renowned computer science and Emeritus of the Art of Computer Programming at Stanford University.Author of the seminal multi-volume work The Art of Computer Programming , Knuth has been called the "father" of the run-time analysis, contributing to the development of, and systematizing formal mathematical techn... . The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Clifford Stein. He is a Full Professor of computer science at Dartmouth College and currently Chair of the Dartmouth College Writing Program.... , Charles E. Leiserson
Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language.... , Ronald L. Rivest, and Clifford Stein
Clifford Stein
Clifford Stein, a computer scientist, is currently a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science.... . Introduction to Algorithms
Introduction to Algorithms
Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ron Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities.... , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp.200–204.
