listsstacksand queues implementation of stacks since stack is listany list implementation will do clearly list and vector support stack operations of the time they are the most reasonable choice occasionally it can be faster to design special-purpose implementation because stack operations are constanttime operationsthis is unlikely to yield any discernable improvement except under very unique circumstances for these special timeswe will give two popular stack implementations one uses linked structureand the other uses an arrayand both simplify the logic in vector and listso we do not provide code linked list implementation of stacks the first implementation of stack uses singly linked list we perform push by inserting at the front of the list we perform pop by deleting the element at the front of the list top operation merely examines the element at the front of the listreturning its value sometimes the pop and top operations are combined into one array implementation of stacks an alternative implementation avoids links and is probably the more popular solution it uses the backpush_backand pop_back implementation from vectorso the implementation is trivial associated with each stack is thearray and topofstackwhich is - for an empty stack (this is how an empty stack is initializedto push some element onto the stackwe increment topofstack and then set thearray[topofstackx to popwe set the return value to thearray[topofstackand then decrement topofstack notice that these operations are performed in not only constant time but very fast constant time on some machinespushes and pops (of integerscan be written in one machine instructionoperating on register with auto-increment and auto-decrement addressing the fact that most modern machines have stack operations as part of the instruction set enforces the idea that the stack is probably the most fundamental data structure in computer scienceafter the array applications it should come as no surprise that if we restrict the operations allowed on listthose operations can be performed very quickly the big surprisehoweveris that the small number of operations left are so powerful and important we give three of the many applications of stacks the third application gives deep insight into how programs are organized balancing symbols compilers check your programs for syntax errorsbut frequently lack of one symbol (such as missing brace or comment startercan cause the compiler to spill out hundred lines of diagnostics without identifying the real error useful tool in this situation is program that checks whether everything is balanced thusevery right bracebracketand parenthesis must correspond to its left counterpart