스택 순열
GfG Practice에서 사용해 보세요. 
산출
산출
빈 스택이 있고 푸시 및 팝 작업을 수행할 수 있습니다. 우리에게는 두 개의 배열이 주어졌습니다. 에이[] 그리고 비[] 여기서 a[]는 요소가 스택에 푸시되는 순서를 나타내고 b[]는 스택에서 요소가 팝되는 순서를 나타냅니다. 주어진 푸시 및 팝 시퀀스가 유효한지 확인합니다.
예:
입력: a[] = [1 2 3] b[] = [2 1 3]
산출: 진실
설명: 1과 2를 누릅니다. b[]에는 2가 필요하므로 먼저 2를 팝하고 그 다음에는 1을 팝합니다. 마지막으로 3을 누르고 터뜨립니다. 푸시 및 팝 시퀀스는 a[] 및 b[]와 일치합니다.입력: a[] = [1 2 3] b[] = [3 1 2]
산출: 거짓
설명: 1 2와 3을 누른 후 필요에 따라 3을 표시할 수 있습니다. 그러나 b[]의 다음 요소는 1이고 스택 상단은 2입니다. 1은 2 아래에서 차단되므로 이 순서를 달성할 수 없습니다.
목차
[순진한 접근 방식] 큐 사용 - O(n) 시간과 O(n) 공간
아이디어는 다음을 사용하여 처리할 나머지 요소를 추적하면서 스택 작업을 시뮬레이션하는 것입니다. 꼬리 .
a[]의 요소를 순서대로 푸시하고 각 요소에 대해 b[]의 앞 부분(예상되는 팝 순서)과 일치하는지 확인합니다. 일치하면 b[]에서 제거합니다. 그렇지 않다면 스택에 밀어 넣습니다. 푸시할 때마다 스택의 상단이 b[]의 앞부분과 일치하는지 확인하고 스택에서 팝하여 b[]에서 제거합니다. 이것을 반복함으로써 b[]의 모든 요소가 일치할 수 있는지 확인합니다. 그렇다면 팝 시퀀스가 유효합니다. 그렇지 않으면 그렇지 않습니다.
C++ #include #include #include #include using namespace std ; bool checkPerm ( vector < int >& a vector < int >& b ) { queue < int > q1 ; for ( int i = 0 ; i < a . size (); i ++ ) q1 . push ( a [ i ]); queue < int > q2 ; for ( int i = 0 ; i < b . size (); i ++ ) q2 . push ( b [ i ]); stack < int > st ; // Dequeue all items one by one while ( ! q1 . empty ()) { int ele = q1 . front (); q1 . pop (); if ( ele == q2 . front ()) { // If matches dequeue from output queue q2 . pop (); // Pop from stack while top matches q2 front while ( ! st . empty () && ! q2 . empty () && st . top () == q2 . front ()) { st . pop (); q2 . pop (); } } else { st . push ( ele ); } } return q2 . empty (); } int main () { vector < int > a = { 1 2 3 }; vector < int > b = { 3 2 1 }; if ( checkPerm ( a b )) cout < < 'true' < < endl ; else cout < < 'false' < < endl ; return 0 ; }
Java import java.util.LinkedList ; import java.util.Queue ; import java.util.Stack ; public class GfG { static boolean checkPerm ( int [] a int [] b ) { Queue < Integer > q1 = new LinkedList <> (); for ( int i = 0 ; i < a . length ; i ++ ) q1 . add ( a [ i ] ); Queue < Integer > q2 = new LinkedList <> (); for ( int i = 0 ; i < b . length ; i ++ ) q2 . add ( b [ i ] ); Stack < Integer > st = new Stack <> (); // Dequeue all items one by one while ( ! q1 . isEmpty ()) { int ele = q1 . poll (); if ( ele == q2 . peek ()) { // If matches dequeue from output queue q2 . poll (); // Pop from stack while top matches q2 front while ( ! st . isEmpty () && ! q2 . isEmpty () && st . peek () == q2 . peek ()) { st . pop (); q2 . poll (); } } else { st . push ( ele ); } } return q2 . isEmpty (); } public static void main ( String [] args ) { int [] a = { 1 2 3 }; int [] b = { 3 2 1 }; if ( checkPerm ( a b )) System . out . println ( 'true' ); else System . out . println ( 'false' ); } }
Python from collections import deque def checkPerm ( a b ): q1 = deque ( a ) q2 = deque ( b ) st = [] # Dequeue all items one by one while q1 : ele = q1 . popleft () if ele == q2 [ 0 ]: # If matches dequeue from output queue q2 . popleft () # Pop from stack while top matches q2 front while st and q2 and st [ - 1 ] == q2 [ 0 ]: st . pop () q2 . popleft () else : st . append ( ele ) return not q2 if __name__ == '__main__' : a = [ 1 2 3 ] b = [ 3 2 1 ] if checkPerm ( a b ): print ( 'true' ) else : print ( 'false' )
C# using System ; using System.Collections.Generic ; public class GfG { static bool checkPerm ( int [] a int [] b ) { Queue < int > q1 = new Queue < int > ( a ); Queue < int > q2 = new Queue < int > ( b ); Stack < int > st = new Stack < int > (); // Dequeue all items one by one while ( q1 . Count > 0 ) { int ele = q1 . Dequeue (); if ( ele == q2 . Peek ()) { // If matches dequeue from output queue q2 . Dequeue (); // Pop from stack while top matches q2 front while ( st . Count > 0 && q2 . Count > 0 && st . Peek () == q2 . Peek ()) { st . Pop (); q2 . Dequeue (); } } else { st . Push ( ele ); } } return q2 . Count == 0 ; } public static void Main () { int [] a = { 1 2 3 }; int [] b = { 3 2 1 }; if ( checkPerm ( a b )) Console . WriteLine ( 'true' ); else Console . WriteLine ( 'false' ); } }
JavaScript function checkPerm ( a b ) { // simulate queue with array let q1 = a ; // simulate queue with array let q2 = b ; let st = []; // pointer for front of q1 let front1 = 0 ; // pointer for front of q2 let front2 = 0 ; while ( front1 < q1 . length ) { let ele = q1 [ front1 ]; front1 ++ ; if ( ele === q2 [ front2 ]) { front2 ++ ; // Pop from stack while top matches q2 front while ( st . length > 0 && st [ st . length - 1 ] === q2 [ front2 ]) { st . pop (); front2 ++ ; } } else { st . push ( ele ); } } return front2 === q2 . length ; } // Driver Code let a = [ 1 2 3 ]; let b = [ 3 2 1 ]; console . log ( checkPerm ( a b ));
산출
true
[예상 접근 방식] Push and Pop 시뮬레이션 - O(n) 시간과 O(n) 공간
이 접근 방식에서는 실제로 대기열을 구축하거나 입력 배열을 수정하지 않습니다. 대신 스택에서 푸시 및 팝 작업을 직접 시뮬레이션합니다.
a[]의 각 요소는 하나씩 스택에 푸시됩니다. 푸시할 때마다 스택의 상단이 b[]의 현재 요소와 일치하는지 확인합니다. 그렇다면 스택에서 이를 팝하고 b[]에서 앞으로 이동합니다. 이 프로세스는 a[]의 모든 요소가 푸시되고 검사될 때까지 반복됩니다. 결국 b[]의 모든 요소가 성공적으로 일치하고 팝되면 순열은 유효합니다(true를 반환). 그렇지 않으면 유효하지 않습니다(false를 반환함).
C++ #include #include #include using namespace std ; bool checkPerm ( vector < int >& a vector < int >& b ) { stack < int > st ; int j = 0 ; for ( int i = 0 ; i < a . size (); i ++ ) { // Push top of a[] to stack st . push ( a [ i ]); // Keep popping from stack while it // matches front of the output queue while ( ! st . empty () && st . top () == b [ j ]) { st . pop (); j ++ ; } } return ( j == b . size ()); } int main () { vector < int > a = { 1 2 3 }; vector < int > b = { 2 1 3 }; cout < < ( checkPerm ( a b ) ? 'true' : 'false' ) < < endl ; return 0 ; }
Java import java.util.Stack ; public class GfG { static boolean checkPerm ( int [] a int [] b ) { Stack < Integer > st = new Stack <> (); int j = 0 ; for ( int i = 0 ; i < a . length ; i ++ ) { // Push top of a[] to stack st . push ( a [ i ] ); // Keep popping from stack while it // matches front of the output array while ( ! st . isEmpty () && st . peek (). equals ( b [ j ] )) { st . pop (); j ++ ; } } return ( j == b . length ); } public static void main ( String [] args ) { int [] a = { 1 2 3 }; int [] b = { 2 1 3 }; System . out . println ( checkPerm ( a b ) ? 'true' : 'false' ); } }
Python def checkPerm ( a b ): st = [] j = 0 for i in range ( len ( a )): # Push top of a[] to stack st . append ( a [ i ]) # Keep popping from stack while it # matches front of the output queue while st and st [ - 1 ] == b [ j ]: st . pop () j += 1 return j == len ( b ) if __name__ == '__main__' : a = [ 1 2 3 ] b = [ 2 1 3 ] print ( 'true' if checkPerm ( a b ) else 'false' )
C# using System ; using System.Collections.Generic ; class GfG { static bool checkPerm ( int [] a int [] b ) { Stack < int > stack = new Stack < int > (); int j = 0 ; for ( int i = 0 ; i < a . Length ; i ++ ) { // Push top of a[] to stack stack . Push ( a [ i ]); // Keep popping from stack while it matches b[j] while ( stack . Count > 0 && stack . Peek () == b [ j ]) { stack . Pop (); j ++ ; } } return j == b . Length ; } static void Main () { int [] a = { 1 2 3 }; int [] b = { 2 1 3 }; Console . WriteLine ( checkPerm ( a b ) ? 'true' : 'false' ); } }
JavaScript function checkPerm ( a b ) { const stack = []; let j = 0 ; for ( let i = 0 ; i < a . length ; i ++ ) { // Push top of a[] to stack stack . push ( a [ i ]); // Keep popping from stack while it // matches front of the output queue while ( stack . length > 0 && stack [ stack . length - 1 ] === b [ j ]) { stack . pop (); j ++ ; } } return j === b . length ; } //Driven Code const a = [ 1 2 3 ]; const b = [ 2 1 3 ]; console . log ( checkPerm ( a b ) ? 'true' : 'false' );
산출
true퀴즈 만들기
