Pythagoras0: /* 노트 */ 새 문단

2020-12-21T14:27:28Z

노트: 새 문단

새 문서

== 노트 ==

===위키데이터===
* ID : [https://www.wikidata.org/wiki/Q177929 Q177929]
===말뭉치===
# In this chapter, you will explore one of the most important data structures which are used in many fields of programming and data handling, i.e., the Stack.<ref name="ref_48973585">[https://www.w3schools.in/data-structures-tutorial/stack/ Concepts of Stack in Data Structure]</ref>
# A stack is a linear data structure in which all the insertion and deletion of data or you can say its values are done at one end only, rather than in the middle.<ref name="ref_48973585" />
# The stack is a linear data structure, and all the insertion and deletion of its values are done in the same end which is called the top of the stack.<ref name="ref_48973585" />
# Let us suppose take the real-life example of a stack of plates or a pile of books etc.<ref name="ref_48973585" />
# and if stack is completely empty, it is said to be .<ref name="ref_73df5cbd">[https://www.tutorialride.com/data-structures/stack-in-data-structure.htm Stack in Data Structure]</ref>
# Stack allows operations at one end only .<ref name="ref_73df5cbd" />
# , for example, in a real life, we can remove a plate or dish from the top of the stack only or while playing a deck of cards, we can place or remove a card from top of the stack only.<ref name="ref_73df5cbd" />
# Similarly, here also, we can only access the top element of a stack.<ref name="ref_73df5cbd" />
# We can't pop an element from the empty stack.<ref name="ref_22299001">[https://www.log2base2.com/data-structures/stack/stack-data-structure.html Application of stack in data structure]</ref>
# If we want to add another item to it, then we add it at the top of the stack as shown in the above figure (left-hand side).<ref name="ref_58692b6e">[https://www.softwaretestinghelp.com/stack-in-cpp/ Stack Data Structure In C++ With Illustration]</ref>
# On the right side, we have shown an opposite operation i.e. we remove an item from the stack.<ref name="ref_58692b6e" />
# This is also done from the same end i.e. the top of the stack.<ref name="ref_58692b6e" />
# This makes the stack to follow LIFO order.<ref name="ref_58692b6e" />
# In this article we are going to explore a very common data structure in programming — the stack.<ref name="ref_2e5b0560">[https://levelup.gitconnected.com/the-stack-data-structure-what-is-it-and-how-is-it-used-in-javascript-23562fb8a590 The stack data structure — What is it and how is it used in JavaScript?]</ref>
# A stack is a linear data structure, elements are stacked on top of each other.<ref name="ref_2e5b0560" />
# Only the last element added can be accessed, i.e the element at the top of the stack.<ref name="ref_2e5b0560" />
# A common analogy of a data stack is a pile (or stack!) of plates in a canteen; plates are stacked on top of each other.<ref name="ref_2e5b0560" />
# A stack is an Abstract Data Type (ADT), commonly used in most programming languages.<ref name="ref_2574e73f">[https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm Data Structure and Algorithms]</ref>
# A real-world stack allows operations at one end only.<ref name="ref_2574e73f" />
# For example, we can place or remove a card or plate from the top of the stack only.<ref name="ref_2574e73f" />
# Likewise, Stack ADT allows all data operations at one end only.<ref name="ref_2574e73f" />
# Stack is a linear data structure which follows a particular order in which the operations are performed.<ref name="ref_5b374022">[https://www.geeksforgeeks.org/stack-data-structure/ Stack Data Structure]</ref>
# 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.<ref name="ref_5b374022" />
# The stack abstract data type is defined by the following structure and operations.<ref name="ref_bbd6b37c">[https://runestone.academy/runestone/books/published/pythonds/BasicDS/TheStackAbstractDataType.html 4.4. The Stack Abstract Data Type — Problem Solving with Algorithms and Data Structures]</ref>
# Stack() creates a new stack that is empty.<ref name="ref_bbd6b37c" />
# push(item) adds a new item to the top of the stack.<ref name="ref_bbd6b37c" />
# pop() removes the top item from the stack.<ref name="ref_bbd6b37c" />
# Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).<ref name="ref_eaae1ddc">[https://www.studytonight.com/data-structures/stack-data-structure Stack Data Structure]</ref>
# push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack.<ref name="ref_eaae1ddc" />
# Both insertion and removal are allowed at only one end of Stack called Top.<ref name="ref_eaae1ddc" />
# The simplest application of a stack is to reverse a word.<ref name="ref_eaae1ddc" />
# A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle.<ref name="ref_2afefb45">[https://www.javatpoint.com/data-structure-stack javatpoint]</ref>
# Stack has one end, whereas the Queue has two ends (front and rear).<ref name="ref_2afefb45" />
# It contains only one pointer top pointer pointing to the topmost element of the stack.<ref name="ref_2afefb45" />
# Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack.<ref name="ref_2afefb45" />
# A pointer called TOP is used to keep track of the top element in the stack.<ref name="ref_704f81aa">[https://www.programiz.com/dsa/stack Stack Data Structure]</ref>
# Although stack is a simple data structure to implement, it is very powerful.<ref name="ref_704f81aa" />
# The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out).<ref name="ref_004f1dd2">[https://en.wikipedia.org/wiki/Stack_(abstract_data_type) Stack (abstract data type)]</ref>
# The name "stack" for this type of structure comes from the analogy to a set of physical items stacked on top of each other.<ref name="ref_004f1dd2" />
# Considered as a linear data structure, 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.<ref name="ref_004f1dd2" />
# This data structure makes it possible to implement a stack as a singly linked list and a pointer to the top element.<ref name="ref_004f1dd2" />
# Adds an item in the stack.<ref name="ref_d0210794">[https://www.geeksforgeeks.org/stack-data-structure-introduction-program/ Stack Data Structure (Introduction and Program)]</ref>
# If the stack is full, then it is said to be an Overflow condition.<ref name="ref_d0210794" />
# Removes an item from the stack.<ref name="ref_d0210794" />
# If the stack is empty, then it is said to be an Underflow condition.<ref name="ref_d0210794" />
# The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item off the stack in order to remove things from it.<ref name="ref_df1c8eaa">[https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues Data Structures/Stacks and Queues]</ref>
# They are 1) inserting an item into a stack (push).<ref name="ref_df1c8eaa" />
# 2) deleting an item from the stack (pop).<ref name="ref_df1c8eaa" />
# Operations push( new-item :item-type) Adds an item onto the stack.<ref name="ref_df1c8eaa" />
# In Data Structures, a Stack is an abstract data type that serves as a collection of items.<ref name="ref_af9b41a7">[https://dev.to/erickarugu/implementing-the-stack-data-structure-in-javascript-59n5 How to Implement the Stack Data Structure in Javascript]</ref>
# Due to its behavior, the stack is called a LIFO data structure.<ref name="ref_af9b41a7" />
# The pop method, on the other hand, removes the topmost element from the stack and returns it.<ref name="ref_af9b41a7" />
# First, we initialize a new instance of the stack by using the "new" keyword and assign that to a variable.<ref name="ref_af9b41a7" />
# A stack is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end.<ref name="ref_a1391e2b">[https://bradfieldcs.com/algos/stacks/introduction/ Introduction to Stacks]</ref>
# The most recently added item is always on the top of the stack and thus will be removed first.<ref name="ref_a1391e2b" />
# Consider a stack of plates on a table, where it’s only possible to add or remove plates to or from the top.<ref name="ref_a1391e2b" />
# Or imagine a stack of books on a desk.<ref name="ref_a1391e2b" />
# A stack is a linear data structure that follows a particular order of operations.<ref name="ref_a23a31a4">[https://learn.saylor.org/mod/page/view.php?id=19023 CS201: The Stack Data Structure]</ref>
# If the stack is full, then it is said to be an overflow condition.<ref name="ref_a23a31a4" />
# If the stack is empty, then it is said to be an underflow condition.<ref name="ref_a23a31a4" />
# The plate at the top is the first one to be removed -- that is, the plate at the bottom remains in the stack for the longest period of time.<ref name="ref_a23a31a4" />
# A stack is a collection of objects that are inserted and removed according to the last-in first-out ( LIFO ) principle.<ref name="ref_0b8e4858">[https://www.cpp.edu/~ftang/courses/CS240/lectures/stack.htm CS240: Data Structures & Algorithms I]</ref>
# Objects can be inserted into a stack at any time, but only the most recently inserted object can be removed at any time.<ref name="ref_0b8e4858" />
# Basically, a stack is a data structure of ordered items such that items can be inserted and removed only at one end (called the top ).<ref name="ref_0b8e4858" />
# A stack is a collection of objects that supports fast last-in, first-out (LIFO) semantics for inserts and deletes.<ref name="ref_72b8b8f0">[https://dbader.org/blog/stacks-in-python Stacks in Python – dbader.org]</ref>
# A useful real-world analogy for a stack data structure is a stack of plates: New plates are added to the top of the stack.<ref name="ref_72b8b8f0" />
# To reach the plates lower down in the stack the topmost plates must be removed one by one.<ref name="ref_72b8b8f0" />
# With a queue you remove the item least recently added (first-in, first-out or FIFO); and with a stack you remove the item most recently added (last-in, first-out or LIFO).<ref name="ref_72b8b8f0" />
# The distinguishing characteristic of a stack is that the addition or removal of items takes place at the same end.<ref name="ref_7a7d165c">[https://brilliant.org/wiki/stacks/ Brilliant Math & Science Wiki]</ref>
# The principle by which a stack is ordered is called LIFO (shorthand for last-in first-out).<ref name="ref_7a7d165c" />
# Sometimes, a stack is implemented to have a maximum capacity.<ref name="ref_7a7d165c" />
# In those cases, if the allocated space for a stack is completely used, then no more elements can be pushed, any attempt to do so will result in an stack overflow error.<ref name="ref_7a7d165c" />
# In this section, we introduce two closely-related data types for manipulating arbitrarily large collections of objects: the stack and the queue.<ref name="ref_885e8597">[https://introcs.cs.princeton.edu/java/43stack/ Stacks and Queues]</ref>
# A stack is a collection that is based on the last-in-first-out (LIFO) policy.<ref name="ref_885e8597" />
# By tradition, we name the stack insert methodand the stack remove operation.<ref name="ref_885e8597" />
# ArrayStackOfStrings.java implements this approach for a stack of strings whose maximum capacity is specified by the argument to the constructor.<ref name="ref_885e8597" />
# A stack is an abstract data type (ADT), commonly used in most programming languages.<ref name="ref_b547e379">[https://medium.com/@gustho/data-structure-stack-1e85e2fbae0c Data Structure — Stack]</ref>
# For example, we can place or remove a card or plate from top of the stack only.<ref name="ref_b547e379" />
# A stack can be implemented by means of Array, Structure, Pointer and Linked-List.<ref name="ref_b547e379" />
# − pushing (storing) an element on the stack.<ref name="ref_b547e379" />
# Like most of the data structures, the stack also represent real-world objects.<ref name="ref_522bfd13">[https://towardsdatascience.com/stack-and-array-implementation-with-python-and-nodejs-b8b260229e3a Stack and Array Implementation with Python and NodeJs]</ref>
# A stack can be implemented using an array, a list, a pointer, etc.<ref name="ref_522bfd13" />
# Once you defined the stack class one of the main functionalities is push function.<ref name="ref_522bfd13" />
# if the stack is full(assume that the list is implemented based on a dynamic array) for the given size or not.<ref name="ref_522bfd13" />
# When you have a whole pile of plates, you can only add a new plate on top of the pile, aka the top of the stack.<ref name="ref_f8ece065">[https://medium.com/@angeloacebedo/data-structures-stacks-and-queues-7cc8790b9ce8 Abstract Data Types: Stacks and Queues]</ref>
# The 2 most important methods in a stack are push() and pop().<ref name="ref_f8ece065" />
# Just like a stack of plates, you can only add — push() — and remove — pop() — from the top of the stack.<ref name="ref_f8ece065" />
# All stacks require only one pointer looking to the end of the stack.<ref name="ref_f8ece065" />
# Theclass represents a last-in-first-out (LIFO) stack of objects.<ref name="ref_6f18b171">[https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html Stack (Java Platform SE 7 )]</ref>
# It extends classwith five operations that allow a vector to be treated as a stack.<ref name="ref_6f18b171" />
# A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.<ref name="ref_6f18b171" />
# A stack is a linear data structure that follows a particular order for the insertion and manipulation of data.<ref name="ref_2fd7dd0a">[https://www.journaldev.com/36920/stack-data-structure Understanding the Stack Data Structure]</ref>
# : This function adds data elements to the stack.<ref name="ref_2fd7dd0a" />
# It removes the top element from the stack.<ref name="ref_2fd7dd0a" />
# Note: We have set a pointer element called ‘top‘ to keep the account of the topmost element in the stack.<ref name="ref_2fd7dd0a" />
# You already know that stacks are used to implement functions and you have seen that each running program has a stack and how a program's stack grows and shrinks during calls to functions/procedures.<ref name="ref_26f15607">[https://www.cse.unr.edu/~sushil/class/cs202/notes/stacks/stacks.html Stacks]</ref>
# A pile of books, a stack of dinner plates, a box of pringles potato chips can all be thought of examples of stacks.<ref name="ref_26f15607" />
# As an abstract entity, a stack is defined by the operations of adding items to the stack, push(), and the operation of removing items from the stack, pop().<ref name="ref_26f15607" />
# There are a couple of other incidentals, that we need to take care of such as not push() ing an item onto a full stack and not trying to pop() items from an empty stack.<ref name="ref_26f15607" />
# On the other hand, the Stack Data Structure does not allow you to store data where you want i.e. order is important.<ref name="ref_574b31a8">[https://www.pascal-programming.info/articles/stack.php Pascal Programming: Articles]</ref>
# The stack is a simple array which stores data items using an index which points to the last element that has been inserted.<ref name="ref_574b31a8" />
# If data is requested from the stack, the last element that has been stored is 'poped' out of the array and returned.<ref name="ref_574b31a8" />
# When popping occurs, the last element is returned and discarded from the stack with the top pointer being decremented by 1.<ref name="ref_574b31a8" />
# That is, the last data element stored in a stack is the first data element retrieved from the stack.<ref name="ref_6214196d">[http://icarus.cs.weber.edu/~dab/cs1410/textbook/7.Arrays/stack.html 7.10. Stacks And Stack Operations]</ref>
# So a stack supports two basic operations: push and pop.<ref name="ref_6214196d" />
# A new data element is stored by pushing it on the top of the stack.<ref name="ref_6214196d" />
# We will use one of the ways of building a stack as an example of how to create and use arrays.<ref name="ref_6214196d" />
# Again, since we only have access to the element at the top of the stack, there’s only one element that we can remove.<ref name="ref_c34a48c4">[https://afteracademy.com/blog/stack-and-its-basic-operations Stack and its basic Operations]</ref>
# We just remove the top of the stack.<ref name="ref_c34a48c4" />
# Peek operation allows the user to see the element on the top of the stack.<ref name="ref_c34a48c4" />
# To prevent performing operations on an empty stack, the programmer is required to internally maintain the size of the stack which will be updated during push and pop operations accordingly.<ref name="ref_c34a48c4" />
# Another way of storing data is in a stack.<ref name="ref_4d1052c8">[https://www.cs.auckland.ac.nz/software/AlgAnim/stacks.html Data Structures and Algorithms: Stacks]</ref>
# (s is a stack created by a call to ConsStack) && (existing item count < max_items) && (item !<ref name="ref_4d1052c8" />
# A stack is simply another collection of data items and thus it would be possible to use exactly the same specification as the one used for our general collection.<ref name="ref_4d1052c8" />
# As a function calls another function, first its arguments, then the return address and finally space for local variables is pushed onto the stack.<ref name="ref_4d1052c8" />
# A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop.<ref name="ref_c6239575">[https://www.bogotobogo.com/Algorithms/stacks.php Stack Data Structure]</ref>
# The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty.<ref name="ref_c6239575" />
# A stack is a restricted data structure, because only a small number of operations are performed on it.<ref name="ref_c6239575" />
# The nature of the pop and push operations also means that stack elements have a natural order.<ref name="ref_c6239575" />
# In Computer Science also, a stack is a data structure which follows the same kind of rules i.e., the most recently added item is removed first.<ref name="ref_c9346a4c">[https://www.codesdope.com/course/data-structures-stacks/ Stack Data Structure Using Array and Linked List]</ref>
# Since a stack just has to follow the LIFO policy, we can implement it using a linked list as well as with an array.<ref name="ref_c9346a4c" />
# A stack supports few basic operations and we need to implement all these operations (either with a linked list or an array) to make a stack.<ref name="ref_c9346a4c" />
# → The push operation adds a new element to the stack.<ref name="ref_c9346a4c" />
# Please note, that the Java Stack class is a subclass of Vector, an older Java class which is synchronized.<ref name="ref_99b12ff2">[http://tutorials.jenkov.com/java-collections/stack.html Java Stack]</ref>
# This synchronization adds a small overhead to calls to all methods of a Stack.<ref name="ref_99b12ff2" />
# A Stack is a data structure where you add elements to the "top" of the stack, and also remove elements from the top again.<ref name="ref_99b12ff2" />
# To use a Java Stack you must first create an instance of the Stack class.<ref name="ref_99b12ff2" />
# In this post, we will see how to implement a stack data structure using queue in C++, Java and Python.<ref name="ref_d924c8e1">[https://www.techiedelight.com/Category/Stack/ Stack Data Structure Problems]</ref>
# In other words, design a stack that supports push and pop operations using standard enqueue and dequeue operations of the queue.<ref name="ref_d924c8e1" />
# The stack implementation has a few big drawbacks: it doesn't have an interface and it extends the Vector class, which has thread synchronization overhead.<ref name="ref_678cd555">[https://www.interviewcake.com/concept/java/stack Stack Data Structure]</ref>
# Hey there, you might have landed here searching for Stack in Python, well, we have got it sorted for you.<ref name="ref_5f91f327">[https://www.edureka.co/blog/stack-in-python/ What is Python Stack and how to Implement it]</ref>
# Similar to a stack of plates at a restaurant, elements in a stack are added or removed from the top of the stack, in a “last in, first out” order.<ref name="ref_5f91f327" />
# To understand Stack at the ground level, think about a pile of books.<ref name="ref_5f91f327" />
# We can record every action of the user by pushing it to the stack.<ref name="ref_5f91f327" />
# For example, suppose we had an operation called ‘pop’ that took a stack as an argument and modified it.<ref name="ref_7f52aa1e">[https://softwareengineering.stackexchange.com/questions/148747/abstract-data-type-and-data-structure Abstract Data Type and Data Structure]</ref>
# Let us conceptualize stacks using a stack of plates placed in a box.<ref name="ref_fd7aa65a">[https://www.educative.io/blog/data-structures-stack-queue-java-tutorial Data Structures 101: how to use Stacks and Queues in Java]</ref>
# A simple real-world application of a stack is reversing a string letter by letter.<ref name="ref_fd7aa65a" />
# When an element is inserted into a stack, it takes the top position and the variable storing this position points to the number below it.<ref name="ref_fd7aa65a" />
# A list-like structure that can be used to solve many problems in computing is the stack.<ref name="ref_969e0235">[https://www.oreilly.com/library/view/data-structures-and/9781449373931/ch04.html Data Structures and Algorithms with JavaScript [Book]]</ref>
# Stacks are efficient data structures because data can be added or removed only from the top of a stack, making these procedures fast and easy to implement.<ref name="ref_969e0235" />
# A stack is a list of elements that are accessible only from one end of the list, which is called the top .<ref name="ref_969e0235" />
# Trays are always removed from the top, and when trays are put back on the stack after being washed, they are placed on the top of the stack.<ref name="ref_969e0235" />
# So, it makes sense to define a new stack data type that ensures that programmers only interact with the data type in acceptable ways.<ref name="ref_92c5cd4c">[https://classes.cs.uchicago.edu/archive/2019/fall/30121-1/lecture-examples/Stacks_and_Stock_Span.html Stacks and Queues]</ref>
===소스===
<references />

스택 - 편집 역사

2021년 2월 17일 (수) 08:01에 Pythagoras0님의 편집

Pythagoras0: /* 메타데이터 */ 새 문단

Pythagoras0: /* 노트 */ 새 문단

@@ 150번째 줄: / 150번째 줄: @@
   <references />
-== 메타데이터 ==
+==메타데이터==
 ===위키데이터===
 * ID :  [https://www.wikidata.org/wiki/Q177929 Q177929]

← 이전 판		2020년 12월 26일 (토) 12:14 판
149번째 줄:		149번째 줄:
	===소스===		===소스===
	<references />		<references />
		+
		+	== 메타데이터 ==
		+
		+	===위키데이터===
		+	* ID : [https://www.wikidata.org/wiki/Q177929 Q177929]