Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).Mainly the following three basic operations are performed in the stack:. Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition. Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.
Algorithm and Program for PUSH and POP Operation on Stack. The Push and Pop functions perform these two tasks. The code adds DisplayStack to make it easier to see the stack content as needed. The remaining code exercises the stack (demonstrates its functionality) by pushing values onto it and then removing them.
Peek or Top: Returns top element of stack. isEmpty: Returns true if stack is empty, else false.
How to understand a stack practically?There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate which is at the top is the first one to be removed, i.e. The plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.Time Complexities of operations on stack:push, pop, isEmpty and peek all take O(1) time. We do not run any loop in any of these operations.Applications of stack:.
/Prefix conversion. Redo-undo features at many places like editors, photoshop. Forward and backward feature in web browsers. Used in many algorithms like,.
Other applications can be Backtracking, and. In Graph Algorithms like andImplementation:There are two ways to implement a stack:. Using array. Using linked listImplementing Stack using Arrays.
Simple representation of a stack runtime with push and pop operations.In, a stack is an that serves as a of elements, with two principal operations:. push, which adds an element to the collection, and. pop, which removes the most recently added element that was not yet removed.The order in which elements come off a stack gives rise to its alternative name, LIFO ( last in, first out). Additionally, a operation may give access to the top without modifying the stack. The name 'stack' for this type of structure comes from the analogy to a set of physical items stacked on top of each other, which makes it easy to take an item off the top of the stack, while getting to an item deeper in the stack may require taking off multiple other items first.Considered as a, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack.
This makes it possible to implement a stack as a and a pointer to the top element. A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an state.
The pop operation removes an item from the top of the stack.A stack is needed to implement. See also:Stacks entered the computer science literature in 1946, when used the terms 'bury' and 'unbury' as a means of calling and returning from subroutines. Subroutines had already been implemented in 's in 1945.and of proposed the idea in 1955 and filed a patent in 1957, and in March 1988 Bauer received the for the invention of the stack principle.
The same concept was developed, independently, by the Australian in the first half of 1954.Stacks are often described by analogy to a spring-loaded stack of plates in a cafeteria. Clean plates are placed on top of the stack, pushing down any already there. When a plate is removed from the stack, the one below it pops up to become the new top.Non-essential operations In many implementations, a stack has more operations than 'push' and 'pop'. An example is 'top of stack', or 'peek', which observes the top-most element without removing it from the stack.
Since this can be done with a 'pop' and a 'push' with the same data, it is not essential. An underflow condition can occur in the 'stack top' operation if the stack is empty, the same as 'pop'. Also, implementations often have a function which just returns whether the stack is empty.Software stacks Implementation A stack can be easily implemented either through an or a. What identifies the data structure as a stack in either case is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations.
The following will demonstrate both implementations, using.Array An array can be used to implement a (bounded) stack, as follows. The first element (usually at the ) is the bottom, resulting in array0 being the first element pushed onto the stack and the last element popped off. The program must keep track of the size (length) of the stack, using a variable top that records the number of items pushed so far, therefore pointing to the place in the array where the next element is to be inserted (assuming a zero-based index convention). ( setf stack ( list 'a 'b 'c ));; set the variable 'stack' ( A B C ) ( pop stack );; get top (leftmost) element, should modify the stack A stack;; check the value of stack ( B C ) ( push 'new stack );; push a new top onto the stack ( NEW B C )Several of the container types have pushback and popback operations with LIFO semantics; additionally, the stack template class adapts existing containers to provide a restricted with only push/pop operations. PHP has an class. Java's library contains a class that is a specialization of.
Following is an example program in language, using that class. A typical stack, storing local data and call information for nested procedure calls (not necessarily ). This stack grows downward from its origin. The stack pointer points to the current topmost on the stack. A push operation decrements the pointer and copies the data to the stack; a pop operation copies data from the stack and then increments the pointer. Each procedure called in the program stores procedure return information (in yellow) and local data (in other colors) by pushing them onto the stack.
This type of stack implementation is extremely common, but it is vulnerable to attacks (see the text).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. Main article:The architecture is an example of a set of registers organised as a stack where direct access to individual registers (relative the current top) is also possible. As with stack-based machines in general, having the top-of-stack as an implicit argument allows for a small footprint with a good usage of and, but it also prevents some types of optimizations possible on processors permitting to the for all (two or three) operands. A stack structure also makes implementations with (for ) somewhat more complex to implement, although it is still feasible, as exemplified by modern implementations., and are all examples of architectures using within a register-stack as another strategy to avoid the use of slow main memory for function arguments and return values.There are also a number of small microprocessors that implements a stack directly in hardware and some have a fixed-depth stack that is not directly accessible.
Examples are the, the, the line, and the. Many stack-based microprocessors were used to implement the programming language at the level. Stacks were also used as a basis of a number of. Such machines were called, the most famous being the.Applications of stacks Expression evaluation and syntax parsing Calculators employing use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations and conversion from one form to another may be accomplished using a stack.
Many compilers use a stack for parsing the syntax of expressions, program blocks etc. Before translating into low level code. Most programming languages are, allowing them to be parsed with stack based machines.Backtracking.
Main article:Another important application of stacks is. Consider a simple example of finding the correct path in a maze. There are a series of points, from the starting point to the destination. We start from one point. To reach the final destination, there are several paths. Suppose we choose a random path. After following a certain path, we realise that the path we have chosen is wrong.
So we need to find a way by which we can return to the beginning of that path. This can be done with the use of stacks. With the help of stacks, we remember the point where we have reached. This is done by pushing that point into the stack. In case we end up on the wrong path, we can pop the last point from the stack and thus return to the last point and continue our quest to find the right path. This is called backtracking.The prototypical example of a backtracking algorithm is, which finds all vertices of a graph that can be reached from a specified starting vertex.Other applications of backtracking involve searching through spaces that represent potential solutions to an optimization problem. Is a technique for performing such backtracking searches without exhaustively searching all of the potential solutions in such a space.Compile time memory management.
Main articles: andA number of are, 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, has a return stack and an operand stack, and also has a graphics state stack and a dictionary stack. Many are also stack-oriented, including the and the.Almost all —the ways in which receive their parameters and return results—use a special stack (the ') 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. The functions 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 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 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.Efficient algorithms Several use a stack (separate from the usual function call stack of most programming languages) as the principle with which they organize their information.These include:., an algorithm for the of a two-dimensional system of points. A convex hull of a subset of the input is maintained in a stack, which is used to find and remove concavities in the boundary when a new point is added to the hull. Part of the for finding the row minima of a monotone matrix uses stacks in a similar way to Graham scan., the problem of finding, for each number in an array, the closest preceding number that is smaller than it.
One algorithm for this problem uses a stack to maintain a collection of candidates for the nearest smaller value. For each position in the array, the stack is popped until a smaller value is found on its top, and then the value in the new position is pushed onto the stack. The, a method for based on maintaining a stack of clusters, each of which is the nearest neighbor of its predecessor on the stack. When this method finds a pair of clusters that are mutual nearest neighbors, they are popped and merged.Security Some computing environments use stacks in ways that may make them vulnerable to 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 a attack that takes 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.This type of attack is a variation on the attack and is an extremely frequent source of security breaches in software, mainly because some of the most popular compilers 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.See also. By contrast, a simple QUEUE operates FIFO. ^;;; (2009) 1990. MIT Press and McGraw-Hill. Carpenter, B. E.; Doran, R. (January 1977).
'The other Turing machine'. The Computer Journal. 20 (3): 269–279. Dr. Friedrich Ludwig Bauer and Dr.
Klaus Samelson (30 March 1957). Germany, Munich: Deutsches Patentamt. Retrieved 2010-10-01. Cite journal requires journal=., Technical University of Munich, Faculty of Computer Science, (1 January 1989). C. Hamblin, 'An Addressless Coding Scheme based on Mathematical Notation', May 1957 (typescript). Ball, John A.
Cambridge, Massachusetts, USA:,. Godse, A. P.; Godse, D. Technical Publications. Retrieved 2015-01-30.
Horowitz, Ellis: 'Fundamentals of Data Structures in Pascal', page 67. Computer Science Press, 1984. Graham, R.L. Information Processing Letters 1, 132-133. Aggarwal, Alok;;;; Wilber, Robert (1987), 'Geometric applications of a matrix-searching algorithm', Algorithmica, 2 (2): 195–208,:,. Berkman, Omer; Schieber, Baruch; (1993), 'Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values', Journal of Algorithms, 14 (3): 344–370,:.
Murtagh, Fionn (1983), (PDF), The Computer Journal, 26 (4): 354–359,:. This article incorporates from the document: Black, Paul E.Further reading., Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.External links Wikimedia Commons has media related to.Wikibooks has a book on the topic of:.
(322 KB).